def solution(n: int, a: list, b: list) -> int:
    mod = int(1e9 + 7)

    a = [0] + a
    b = [0] + b
    f = [[0] * 3 for _ in range(n + 1)]
    for i in range(1, n + 1):
        a[i] %= 3
        b[i] %= 3

    f[0][0] = 1
    for i in range(1, n + 1):
        for j in range(3):
            f[i][j] = (f[i - 1][(j + 3 - a[i]) % 3] + f[i - 1][(j + 3 - b[i]) % 3]) % mod

    return f[n][0]


if __name__ == '__main__':
    print(solution(n = 3 ,a = [1, 2, 3] ,b = [2, 3, 2]) == 3)
    print(solution(n = 4 ,a = [3, 1, 2, 4] ,b = [1, 2, 3, 1]) == 6)
    print(solution(n = 5 ,a = [1, 2, 3, 4, 5] ,b = [1, 2, 3, 4, 5]) == 32)
